home *** CD-ROM | disk | FTP | other *** search
/ Aminet 45 / Aminet 45 (2001)(GTI - Schatztruhe)[!][Oct 2001].iso / Aminet / dev / src / adasort.lha / Sort.adb < prev    next >
Text File  |  2001-08-28  |  2KB  |  80 lines
  1. --
  2. --  Elementare Sortieralgorithmen in Ada
  3. --  Norman Walter, Universität Stuttgart
  4. --  Datum: 25.8.2001
  5. --
  6.  
  7. with text_io,ada.integer_text_io;
  8. use  text_io,ada.integer_text_io;
  9.  
  10. package body Sort is
  11.  
  12. Procedure Display (A: in Feld_Typ) is
  13. -- Gibt komplettes Array aus
  14.  
  15. begin
  16.  
  17.    for i in A'First..A'Last loop
  18.      put(character'val(A(i))&" ");
  19.      -- Die Integer Werte werden hier als ASCII Zeichen ausgegeben
  20.    end loop;
  21.    New_Line;
  22.  
  23. end Display;
  24.  
  25. Procedure Swap (A,B: in out Element_Typ) is
  26. -- Vertauscht zwei Elemente
  27. T: Element_Typ := A;
  28. begin
  29.     A:=B;
  30.     B:=T;
  31. end Swap;
  32.  
  33. Procedure Bubble_Sort (Sort_Array: in out Feld_Typ) is
  34.  
  35.  --  Bubble Sort Algorithmus
  36.  --  Eigenschaften: Bubble Sort benötigt im Durchschnitt
  37.  --  und im ungünstigsten Fall ungefähr N^2/2 Vergleiche
  38.  --  und N^2/2 Austauschoperationen.
  39.  
  40. begin
  41.  
  42.     for Unsorted in reverse Sort_Array'First .. Sort_Array'Last - 1 loop
  43.             for j in Sort_Array'First .. Unsorted loop
  44.                 if Sort_Array (j) > Sort_Array (j+1) then
  45.                     -- Sortieren durch direktes Austauschen
  46.                     Swap (Sort_Array (j), Sort_Array (j+1));
  47.                     Display(Sort_Array);
  48.                end if;
  49.             end loop;
  50.       end loop;
  51.  
  52. end Bubble_Sort;
  53.  
  54. Procedure Selection_Sort (Sort_Array: in out Feld_Typ) is
  55.  
  56.  --  Eigenschaften: Selection Sort benötigt ungefähr
  57.  --  N^2/2 Vergleiche und N Austauschoperationen.
  58.  --  Für Dateien mit großen Datensätzen und kleinen
  59.  --  Schlüsseln ist Selection Sort linear.
  60.  
  61.   Min : Index_Typ; -- Zur Suche nach dem Minimum
  62.  
  63. begin
  64.  
  65.    for I in Sort_Array'First .. Sort_Array'Last - 1 loop
  66.      -- I gibt an, wohin das gefundene Minimum getauscht werden soll
  67.      Min := I;
  68.      for J in I+1 .. Sort_Array'Last loop
  69.        if Sort_Array (J) < Sort_Array (Min) then
  70.           Min := J; -- Neues Minimum gefunden
  71.        end if;
  72.      end loop;
  73.      Swap (Sort_Array (Min), Sort_Array (I));
  74.      Display(Sort_Array);
  75.    end loop;
  76.  
  77. end Selection_Sort;
  78.  
  79. end Sort;
  80.